#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150005;
int n,m,Q;
int a[N];
int L[N],R[N];
ll ans[N],res[N];
vector<int>q[N];
deque< pair<int,int> >que;
int cur;
void solve1()
{
    for(int i = 1;i <= n;i++)
    {
        if(q[i].empty()) continue;
        que.clear();
        ans[i-1] = 0;
        cur = 0;
        for(int j = i;j <= n;j++)
        {
            ans[j] = ans[j-1];
            if(cur > a[j])
            {
                while(!que.empty())
                {
                    auto p = que.front();que.pop_front();
                    cur -= p.second;
                    if(cur < a[j])
                    {
                        que.push_front(make_pair(p.first,a[j]-cur));
                        cur = a[j];
                    }
                    if(cur == a[j]) break;
                }
            }
            else if(cur < a[j])
            {
                ans[j] += a[j] - cur;
                que.push_back(make_pair(j,a[j]-cur));
                cur = a[j];
            }
            auto p = que.front();
            if(p.first == j-m+1) cur -= p.second,que.pop_front();
            //cout<<p.first<<" "<<p.second<<" "<<j-m+1<<" "<<ans[j]<<" ";
        }
        //cout<<"\n";
        for(auto x:q[i])
        {
            res[x] = ans[R[x]];
        }
    }
    for(int i = 1;i <= Q;i++) cout<<res[i]<<"\n";
    //cout<<"\n";
}
int main()
{
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>Q;
    for(int i = 1;i <= n;i++)
        cin>>a[i];
    for(int i = 1;i <= Q;i++)
    {
        cin>>L[i]>>R[i];
        q[L[i]].push_back(i);
    }
    if(n <= 5000) return solve1(),0;
    bool flag = 0;
    for(int i = 1;i <= n;i++)
        if(a[i] < a[i-1]) flag = 1;
    //if(!flag) return solve2(),0;
    return 0;
}